package tree.leetcode_958_medium;

import java.util.LinkedList;
import java.util.Queue;

public class IsCompleteTree {
    public boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //记录左右孩子是否双全
        boolean isMeet = false;
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            //如果左孩子为null，右孩子不为null，false;
            //遇到第一个左右孩子不双全的节点后，后续节点不是叶子结点，false;
            if(
                //如果左孩子为null，右孩子不为null，false;
                    (node.left == null && node.right != null)
                    ||
                            //遇到第一个左右孩子不双全的节点后，后续节点不是叶子结点，false;
                            (isMeet && (node.left != null || node.right != null))
            ){
                return false;
            }
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
            if(node.left == null || node.right == null){
                isMeet = true;
            }
        }
        return true;
    }
}
